Vương Kiến Bình quê quán ở Tán Hoàng, tỉnh Hà Bắc; sinh ra ở Phủ Thuận, tỉnh Liêu Ninh. Ông gia nhập Quân Giải phóng Nhân dân Trung Quốc năm 1969 vào quân đoàn pháo binh số 40, từng giữ các chức trung đoàn trưởng pháo binh, tham mưu trưởng lữ đoàn rồi lữ đoàn trưởng pháo binh Tập đoàn quân 40. Năm 1992, được bổ nhiệm làm Sư đoàn trưởng sư 120, tập đoàn quân 40. Sau khi Sư đoàn 120 chuyển thành sư đoàn cơ động của Bộ Tư lệnh Cảnh sát vũ trang, ông chuyển sang lực lượng cảnh sát vũ trang (là bộ phận của quân đội cùng với Quân Giải phóng Nhân dân Trung Quốc).Năm 1996, ông được bổ nhiệm làm Tổng đội trưởng Cảnh sát vũ trang Tây Tạng, sau được thăng chức Phó Tham mưu trưởng Bộ tư lệnh Cảnh sát vũ trang. Năm 2006, ông là Tham mưu trưởng Bộ Tư lệnh Cảnh sát vũ trang. Tháng 6 năm 2009, ông được bổ nhiệm làm Phó Tư lệnh, sau đó được chỉ định thay thế tướng Ngô Song Chiến giữ chức Tư lệnh Cảnh sát vũ trang vào tháng 6 năm 2012.[3] Ngày 30 tháng 7 năm 2012, Vương Kiến Bình được phong hàm Thượng tướng. Tháng 12 năm 2014, được điều động giữ chức Phó Tổng Tham mưu trưởng Quân Giải phóng Nhân dân Trung Quốc,[4] đến tháng 1 năm 2015, được giao kiêm nhiệm chức Tổ trưởng tổ lãnh đạo giám sát huấn luyện quân sự toàn quân.[5]

Sau khi ông Tập Cận Bình tiến hành cải tổ quân đội, tháng 1 năm 2016, Vương Kiến Bình được giao giữ chức Phó Tổng Tham mưu trưởng Bộ Tham mưu liên hợp Quân ủy Trung ương mới được thành lập.

Ngày 26 tháng 8 năm 2016, tờ Bưu điện Hoa Nam Buổi sáng (SCMP) của Hong Kong đăng tin cho biết tướng Vương Kiến Bình bị các nhân viên cơ quan Ủy ban kiểm tra kỷ luật Quân ủy Trung ương bắt ngày 25 tháng 8 khi đang đi thị sát ở Thành Đô, bà vợ và thư ký của ông Bình cũng bị bắt giữ cùng ngày tại Bắc Kinh.[6] Tháng 10 năm 2016, Vương Kiến Bình đã không có mặt tại Hội nghị Trung ương 6 khóa XVIII của Đảng Cộng sản Trung Quốc, điều này đã gián tiếp xác nhận việc ông đã bị "ngã ngựa".[7]

Chiều ngày 29 tháng 12 năm 2016, tại cuộc họp báo, ông Dương Vũ Quân, Cục trưởng Tin tức, người phát ngôn của Bộ Quốc phòng Trung Quốc khi trả lời câu hỏi của một phóng viên về sự vắng mặt của Thượng tướng Vương Kiến Bình, Ủy viên Trung ương Đảng, Phó Tổng Tham mưu trưởng Bộ Tham mưu liên hợp Quân ủy, Tư lệnh Bộ Tư lệnh Cảnh sát vũ trang tại Hội nghị Trung ương 6 khóa XVIII và không xuất hiện công khai trong thời gian gần đây, đã xác nhận tin đồn trên mạng xã hội và báo chí hải ngoại về việc ông Vương Kiến Bình bị điều tra. Theo ông Quân: “Vương Kiến Bình đã bị cơ quan kiểm sát quân sự lập hồ sơ điều tra về việc phạm tội nhận hối lộ”.[8]

Vương Kiến Bình là Ủy viên Dự khuyết Ban Chấp hành Trung ương Đảng Cộng sản Trung Quốc khóa XVII, xếp ở vị trí thứ 4 trong số 167 Ủy viên. Tại Đại hội Đảng Cộng sản Trung Quốc lần thứ 18 (tháng 11 năm 2012), ông được bầu làm Ủy viên chính thức Ban Chấp hành Trung ương Đảng Cộng sản Trung Quốc khóa XVIII.